package tree;

public class ZuiJinGongGongZuXian {
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);

        Node n = zuiJinGongGongZuXian(root, root.left.left, root.left.right);
        System.out.println(n.value);
        n = zuiJinGongGongZuXian(root, root.left.left, root.right.left);
        System.out.println(n.value);
        n = zuiJinGongGongZuXian(root, root.left, root.left.right);
        System.out.println(n.value);
    }

    /*
    root是p，或root是q，直接返回root
    从root左子树和右子树，递归各得到一个公共祖先，root就是他们的公共祖先
    只从左侧得到公共祖先，返回这个节点
    只从右侧得到公共祖先，返回这个节点
    返回null

    最简问题：root是null，直接返回null
     */

    private static Node zuiJinGongGongZuXian(Node root, Node p, Node q) {
        if (root == null) {
            return null; //最简问题，没有树，不用执行
        }
        if (root == p || root == q) {
            return root; //root就是要处理的其中一个节点，root就是公共祖先
        }

        //递归，在左子树和右子树中分别寻找
        Node left = zuiJinGongGongZuXian(root.left, p, q);
        Node right = zuiJinGongGongZuXian(root.right, p, q);

        if (left != null && right != null) { //从左右子树各找到个祖先，root才是公共祖先
            return root;
        }
        if (left != null) { //左边找到，该节点就是公共祖先
            return left;
        }
        if (right != null) { //右边找到，该节点就是公共祖先
            return right;
        }
        return null; //没有公共祖先
    }

    //二叉树的节点类
    static class Node {
        int value;
        Node left;
        Node right;

        Node(int value) {
            this.value = value;
        }
    }
}
